Projet: Tri avec une Pile

Chaîne à afficher si l'image ne peut s'afficher
Représentation d'un tri avec une pile.

Présentations des codes

Pour les codes, j'ai décidé d'utiliser une pile avec comme implémentation la liste chaînée.

Code du module Pile


class Maillon:

    def __init__(self, valeur, suivant = None):
        self.valeur = valeur
        self.suivant = suivant
        
class Pile:


    def __init__(self, tete = None):
        self.tete = tete
    def __str__(self):
        copie=self.tete
        v=''
        while copie is not None:
            v = v+str(copie.valeur)+'|'
            #print(v)
            copie=copie.suivant
        return v
    def est_vide(self):
        return self.tete is None
    
    def empiler(self, element):
        self.tete = Maillon(element, self.tete)
        
    
    def depiler(self):
        s= self.tete.valeur
        self.tete = self.tete.suivant
        return  s
    
    def inversion_pile(pile):
        pile_invers=Pile()
        maillon=pile1.sommet
        while maillon.suivant!=None:
            pile_invers.empiler(maillon.valeur)
            maillon=maillon.suivant
        return pile_invers

Code du Tri avec une Pile.


from pile import *


def tri_en_pile(tab: list) -> list:
    """Renvoie une liste trié,
    ATTENTION: Si la liste n'est pas triable, la liste sera quand même renvoyée non triée."""
    pile_temp = Pile()
    pile_resultat = Pile()

    for element in tab:
        while not pile_temp.est_vide() and pile_temp.tete.valeur > element:
            
            pile_resultat.empiler(pile_temp.depiler())

        pile_temp.empiler(element)

    while not pile_temp.est_vide():

        pile_resultat.empiler(pile_temp.depiler())

    tab_sortie = []
    while not pile_resultat.est_vide():

        tab_sortie.append(pile_resultat.depiler())

    return tab_sortie

if __name__ == '__main__':

    print(f"[1, 2, 4, 3] : {tri_en_pile([1, 2, 4, 3])}")
    print("SI TABLEAU NON TRIABLE:")
    print(f"[2,3,1,5,4] : {tri_en_pile([2,3,1,5,4])}")

Problème recontré lors du codage.

Lors du codage, j'ai recontré quelques problèmes, notamment des problèmes de tri et comment le faire: Quels conditions ? Quelles asserts ? les méthodes etc...

Résolution du problème

Dans ce code, nous avons deux piles ,une temporaire ( pile_temp ) et celle qui servira de "résultat" qui sert a mettre les valeurs triés (pile_resultat), qui seront ensuite remit dans une liste final (tab_sortie). Cela est la façon la plus rapide et la plus simple que j'ai pu faire, d'où l'absence d'Assert car sinon le code serait passé d'une complexité dite "amortie" à une complexité en O(n) car on serait obligé de faire une boucle en O(n) pour vérifier l'ordre des valeurs.

Cas si liste triable

Nous renvoie une liste triée.

Cas si liste non triable

Nous renvois une liste non triée faute d'Assert.

Conclusion